package busquedasciegas.anchura;

import java.util.*;

public class PrimeroAnchura {
	
	LinkedList<EstadoPuzzle> visitados;
	
	public PrimeroAnchura(int cuadrados){
		visitados = new LinkedList<EstadoPuzzle>();
	}
	
	/**
	 * Busca en un espacio de búsqueda el estado objetivo o meta
	 * haciendo un recorrido primero en anchura.
	 * @param inicial Representación del estado inicial.
	 * @param meta Representación del estado final.
	 */
	public String buscar(EstadoPuzzle inicial, int[][] meta){
		
		EstadoPuzzle actual;		
		String traza = "";
		LinkedList<EstadoPuzzle> hijos = new LinkedList<EstadoPuzzle>();
		visitados.add(inicial);	
//		System.out.println("Inicial");
//		System.out.println(inicial);
		while (!visitados.isEmpty()){
			actual = visitados.pop();
//			System.out.println("Actual");
//			System.out.println(actual);
			hijos = actual.generarDescendientes();
			
			for (EstadoPuzzle hijo : hijos) {
				if (!visitados.contains(hijo))
					visitados.add(hijo);
//				System.out.println("Hijo");
//				System.out.println(hijo);
				if ((!hijo.isVisitado()) && (!iguales(hijo.tablero, meta))){
					hijo.setVisitado(true);
				}
				else{
					if (iguales(hijo.tablero, meta)){
						traza = hallarTraza(inicial, hijo);
						//System.out.println("Resuelto");
						return traza;
					}
				}
			}
		}
		return traza;
	}
	
	/**
	 * 
	 * @param raiz Representación del estado inicial.
	 * @param meta Representación del estado final, meta u
	 * objetivo.
	 */
	public String hallarTraza(EstadoPuzzle raiz, EstadoPuzzle meta){
		String oper = "";
		EstadoPuzzle actual = meta;
		LinkedList<EstadoPuzzle> sol = new LinkedList<EstadoPuzzle>();
		while (!iguales(raiz.tablero, actual.tablero)){
			sol.add(actual);
			actual = actual.padre;
		}
		sol.add(actual);
		oper = oper + "Solucion: " + "\n";
		int numMov = sol.size();
		for(int i = 0; i < numMov; i++){
			//System.out.println(sol.get(sol.size() - 1));
			oper = oper + sol.pollLast() + "\n";
		}
		return oper;
	}
	
	/**
	 * 
	 * @param a Matriz que representa el tablero del puzzle.
	 * @param b Matriz que representa el tablero del puzzle.
	 * @return Retorna true si las matrices a y b son iguales,
	 * es decir, tienen los mismos elementos.
	 */
	private boolean iguales(int[][] a, int[][] b)
	{
		for (int i = 0; i < a.length; i++){
			for (int j = 0; j < a[0].length; j++){
				if (a[i][j] != b[i][j]){
					return false;
				}
			}
		}
		return true;
	}
	
	public static void main(String[] args) {
		PrimeroAnchura pa = new PrimeroAnchura(9);
		LinkedList<Integer> inicial = new LinkedList<Integer>();
		int[][] meta = new int[3][3];
		meta[0][0] = 1;
		meta[0][1] = 2;
		meta[0][2] = 3;
		//meta[0][3] = 5;
		meta[1][0] = 8;
		meta[1][1] = 0;
		meta[1][2] = 4;
		//meta[1][3] = 8;
		meta[2][0] = 7;
		meta[2][1] = 6;
		meta[2][2] = 5;
		//meta[2][3] = 11;
//		meta[3][0] = 13;
//		meta[3][1] = 14;
//		meta[3][2] = 15;
		//meta[3][3] = 12;
		inicial.add(2);
		inicial.add(8);
		inicial.add(3);
		inicial.add(1);
		inicial.add(6);
		inicial.add(4);
		inicial.add(7);
		inicial.add(0);
		inicial.add(5);
//		inicial.add(10);
//		inicial.add(11);
//		inicial.add(12);
//		inicial.add(13);
//		inicial.add(14);
//		inicial.add(15);
//		inicial.add(0);
		EstadoPuzzle e = new EstadoPuzzle(inicial);
		System.out.print(pa.buscar(e, meta));
	}
	
}
